#include "maxSlidingWindow.h"

std::vector<int> maxSlidingWindow(std::vector<int> &nums, int k) {
    std::priority_queue<std::pair<int, int>> queue;
    std::vector<int> result;
    for (int i = 0; i < k; i++) {
        queue.emplace(nums[i], i);
    }
    result.push_back(queue.top().first);
    for (int i = k; i < nums.size(); i++) {
        queue.emplace(nums[i], i);
        while (i - k >= queue.top().second) {
            queue.pop();
        }
        result.push_back(queue.top().first);
    }
    return result;
}

// std::vector<int> maxSlidingWindow(std::vector<int> &nums, int k) {
//     std::deque<int> queue;
//     std::vector<int> result;
//     for (int i = 0; i < k; i++) {
//         if (i == 0)
//             queue.push(nums[i]);
//         else {
//             while (!queue.empty() && nums[i] > queue.top()) {
//                 nums.pop();
//             }
//             queue.push(nums[i]);
//         }
//     }
//
//     const int n = nums.size();
//     for (int i = 0; i <= n - k; i++) {
//         result.push_back(queue.front());
//         while (!queue.empty() && nums[i] > queue.top) {
//             nums.pop();
//         }
//         queue.push(nums[i]);
//     }
//     return result;
// }
